//给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。 
//
// 注意：两个节点之间的路径长度由它们之间的边数表示。 
//
// 示例 1: 
//
// 输入: 
//
// 
//              5
//             / \
//            4   5
//           / \   \
//          1   1   5
// 
//
// 输出: 
//
// 
//2
// 
//
// 示例 2: 
//
// 输入: 
//
// 
//              1
//             / \
//            4   5
//           / \   \
//          4   4   5
// 
//
// 输出: 
//
// 
//2
// 
//
// 注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。 
// Related Topics 树 深度优先搜索 二叉树 
// 👍 508 👎 0

package com.cute.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

public class LongestUnivaluePath {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(5);
        TreeNode node3 = new TreeNode(2);
        TreeNode node4 = new TreeNode(2);
        TreeNode node5 = new TreeNode(5);
        root.left = node1;root.right = node2;node1.left = node3;node1.right = node4;node2.right = node5;
        new LongestUnivaluePath().new Solution().count(root);
    }
    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    /**
     * 统计的路径数目，不是统计的节点数目
     * 题解中的方法，这种判断方式是挺巧妙的，递归到叶子结点之后返回0
     * 需要在前驱结点的位置进行判断
     * 方法的返回值是最长边长（节点数 - 1 ）
     * 当前节点下一个节点只有两种选择，可以得到left和right的边长
     * 如果当前节点 = 左子节点，那么从左边递归回来的长度可以+1，右子节点同理
     * 返回值为左右子树和当前节点比较之后的最大值
     * 同时需要更新全局最大值
     */
    int ans = 0;
    public int longestUnivaluePath(TreeNode root) {
        count(root);
        return ans;
    }
    public int count(TreeNode node){
        if (node == null) return 0;
        int left = count(node.left);
        int right = count(node.right);
        left = node.left != null && node.val == node.left.val ? left + 1 : 0;
        right = node.right != null && node.val == node.right.val ? right + 1 : 0;
        ans = Math.max(ans, left + right);
        return Math.max(left, right);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}